# 编码最短长度的字符串
# https://leetcode-cn.com/problems/encode-string-with-shortest-length/
# 给定一个 非空字符串，将其编码为具有最短长度的字符串。
#
# 编码规则是：k[encoded_string]，其中在方括号encoded_string 中的内容重复 k 次。
#
# 注：
#
# k为正整数
# 如果编码的过程不能使字符串缩短，则不要对其进行编码。如果有多种编码方式，返回 任意一种 即可
#
#
# 示例 1：
#
# 输入：s = "aaa"
# 输出："aaa"
# 解释：无法将其编码为更短的字符串，因此不进行编码。
# 示例 2：
#
# 输入：s = "aaaaa"
# 输出："5[a]"
# 解释："5[a]" 比 "aaaaa" 短 1 个字符。
# 示例 3：
#
# 输入：s = "aaaaaaaaaa"
# 输出："10[a]"
# 解释："a9[a]" 或 "9[a]a" 都是合法的编码，和 "10[a]" 一样长度都为 5。
# 示例 4：
#
# 输入：s = "aabcaabcd"
# 输出："2[aabc]d"
# 解释："aabc" 出现两次，因此一种答案可以是 "2[aabc]d"。
# 示例 5：
#
# 输入：s = "abbbabbbcabbbabbbc"
# 输出："2[2[abbb]c]"
# 解释："abbbabbbc" 出现两次，但是 "abbbabbbc" 可以编码为 "2[abbb]c"，因此一种答案可以是 "2[2[abbb]c]"。
#
#
# 提示：
#
# 1 <= s.length <= 150
# s 由小写英文字母组成
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/encode-string-with-shortest-length
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
from typing import Optional, Tuple


class Solution1:
    """
    方法1: 这里使用贪婪的策略, s[i:j], 只要能够使用编码获得提升就使用编码
    assert solution1.encode("aaaaaaaaaabbbaaaaabbb") != "5[a]2[5[a]bbb]"
    """

    def encode(self, s: str) -> str:
        return Solution1.encode_rec(s)

    @staticmethod
    def encode_rec(s: str) -> str:
        res = Solution1.find_duplicated(s)
        if len(s) == 0:
            return ''
        if res:
            i, k, nu, _ = res
            sub_str = Solution1.encode_rec(s[i:(i + k)])
            return '%s%d[%s]%s' % (Solution1.encode_rec(s[0:i]), nu, sub_str, Solution1.encode_rec(s[(i + nu * k):]))
        else:
            return s

    @staticmethod
    def find_duplicated(s: str):
        collector = []
        for i in range(len(s)):
            best_k = 0
            k = (len(s) - i) // 2

            while k > 0:
                nu = 2
                lift = 0
                best_nu = 1
                best_lift = 0
                while i + nu * k <= len(s):
                    if s[i:(i + k)] == s[(i + (nu - 1) * k):(i + nu * k)] and best_nu == nu - 1:
                        lift = nu * k - k - len(str(nu)) - 2
                        best_nu = nu

                        if best_lift < lift:
                            best_k = k
                            best_lift = lift
                        # print('i: %d, k: %d, nu: %d, lift: %d, best_nu: %d' % (i, k, nu, lift, best_nu))
                    nu += 1
                if best_lift > 0:
                    collector.append((i, best_k, best_nu, best_lift))
                k -= 1
        return max(collector, key=lambda x: (x[-1], -x[1])) if len(collector) else None


class Solution2:
    """
    https://leetcode-cn.com/problems/encode-string-with-shortest-length/solution/liang-chong-jie-fa-by-jason-2-65/
    leetcode 数据库题目全部题解

解法一 回溯法
解法二 动态规划
解法一 回溯法
本题容易得到的思路是，找出字符串中连续的重复子串。将这些子串编码为题目要求的形式。

连续重复子串是指形如s=”xxxxx…x”的字符串，其中x是子串。

例如：”aaaaaaaaaa”

连续的重复子串是”a”

例如：”aabcaabcd”

其中，”aabcaabc”，有连续的重复子串”aabc”

例如：”abbbabbbcabbbabbbc”

连续的重复子串是 “abbbabbbc”

本题的真正难点在于快速求出字符串中连续的重复子串。

可以想到的方法有，枚举子串逐个查找，用上kmp，lcp类的算法，进行加速。

但是，有一个简便的方法。

对字符串s，s与s拼接成t=s+s。

在t中，从位置1开始查找s。查找到，在位置p处开始，t中出现s。即p=t.find(s,1).

要知道t中一定能查找到s。

当p >= s.size()时，说明s中没有连续重复子串。

当p < s.size()时， s中有连续重复子串。

且连续重复子串是s.substr(0,p)，重复个数为s.length / p.

例如： s=”aabcaabc”

t= “aabcaabcaabcaabc”

p=t.find(s,1)=4

连续重复子串是”aabc”，重复个数为8/4=2。


t=s+s;
p=t.find(s,1);
if(p>=s.length){
    无连续重复子串;
}else{
    sub=s.substr(0,p);
    cnt=s.length/p.length;
}
设s(i,j)表示子串s[i,…,j]。串的长度为len=j-i+1。

用d[i][j]表示s(i,j)的最短编码串。

当len < 5时，s(i,j)不用编码。d[i][j]=s(i,j)

当len > 5时，s(i,j)的编码串有两种可能。

当s(i,j)有连续重复子串时，s(i,j)可编码为”k[重复子串]”的形式.

d[i][j]= “k[重复子串]”

此外，将s(i,j)分成两段s(i,k)和s(k+1,j)，(i <= k <j)。

当d[i][k].length + d[k+1][j].length < d[i][j].length时，

d[i][j] = d[i][k] + d[k+1][j] .


dfs(s,i,j,d){
    len=j-i+1;
    d[i][j]=s(i,j);
    if(len<5) 返回;
    t=s(i,j)+s(i,j);
    p=t.find(s(i,j),1);
    if(p < len){
        d[i][j]=(len/p) +'[' + dfs(s,i,i+p-1,d)+']';
    }
    for(i <= k <j){
        a=dfs(s,i,k,d);
        b=dfs(s,k+1,j,d);
        if(a.length + b.length < d[i][j].length){
            d[i][j]=a+b;
        }
    }
    返回d[i][j];
}
代码：


    string encode(string s) {
        vector<vector<string>> d(s.size(),vector<string>(s.size(),""));
        return dfs(s,0,s.size()-1,d);
    }

    string dfs(const string s,int i,int j,vector<vector<string>>& d){
        if(i > j) return "";
        string& ans=d[i][j];
        if(ans.size()) return ans;
        int len = j-i+1;
        ans=s.substr(i,len);
        if(len < 5) return ans;
        int p=(ans+ans).find(ans,1);
        if(p < len){
            ans=to_string(len/p)+"["+dfs(s,i,i+p-1,d)+"]";
        }
        for(int k=i;k<j;++k){
            string c=dfs(s,i,k,d);
            string e=dfs(s,k+1,j,d);
            if(c.size()+e.size() < ans.size()){
                ans=c+e;
            }
        }
        return ans;
    }
解法二 动态规划
将解法一的递归改为递推。

从短的s(i,j)开始，往长的s(i,j)处计算。

用d[i][j]表示s(i,j)的最短编码串。

同解法一，d[i][j]有两种可能的来源。

1，连续重复子串。

2, 分成两段d[i][k]和d[k+1][j]。


for(len in [1,s.length]){
    for(i=0;i+len <= s.length){
        j=i+len-1;
        d[i][j]=s(i,j);
        if(len >= 5) {
            t=s(i,j)+s(i,j);
            p=t.find(s(i,j),1);
            if(p < len){
                d[i][j]=(len/p) + '[' +d[i][i+p-1]+']';
            }
            for(i <= k < j){
                if(d[i][k].length + d[k+1][j].length < d[i][j].length){
                    d[i][j] = d[i][k] + d[k+1][j];
                }
            }
        }
    }
}
代码：


    string encode(string s) {
        vector<vector<string>> d(s.size(),vector<string>(s.size(),""));
        for(int len=1;len<=s.size();++len){
            for(int i=0;i+len<=s.size();++i){
                const int j=i+len-1;
                string& ans=d[i][j];
                ans=s.substr(i,len);
                if(len >= 5){
                    int p=(ans+ans).find(ans,1);
                    if(p < ans.size()){
                        ans=to_string(ans.size()/p)+"["+d[i][i+p-1]+"]";
                    }
                    for(int k=i;k<j;++k){
                        if(d[i][k].size()+d[k+1][j].size() < ans.size()){
                            ans=d[i][k] + d[k+1][j];
                        }
                    }
                }
            }
        }
        return d[0][s.size()-1];
    }


作者：jason-2
链接：https://leetcode-cn.com/problems/encode-string-with-shortest-length/solution/liang-chong-jie-fa-by-jason-2-65/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

理解:
假设
- 字符串的s[i:j]有自己的最短编码d[i][j]
- s[i:j]最短编码有三种情况, 一种是不变, 一种是某字符串的n倍, 另一种是拆分为s[i:k] + s[k:j]再分别编码
- 如果s[i:j]长度小于5肯定不变

伪代码:
d[i][j] = j - i
# 下面这样不行, 因为d[k][j]这一步会用到第二个循环外的, 如i=0, j=10, k=2时, d[2][10]还未形成
# -----
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        if j - i <= 4:
            break
        n, loc = find_mini_divisor(s[i:j])
        res = '%d[%s]' % (n, d[i][loc])
        max(range(i + 1, j), len(d[i][k] + d[k][j]))

# 分析
#   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
# 0 |   |   |   |   |   |   |   |   |   |   |
# 1 |   |   |   |   |   |   |   |   |   |   |
# 2 |   |   |   | - | * |   | * |   |   |   |
# 3 |   |   |   |   |   |   | - |   |   |   |
# 4 |   |   |   |   |   |   | * |   |   |   |
# 5 |   |   |   |   |   |   |   |   |   |   |
# 6
# ----
# d[2][6] = d[2][4] + d[4][6]
for size in range(5, len(s)):
    for i in range(len(s)):
        j =  i + size
        if j > len(s):
            break
        res = s[i:j]
        n, loc = find_mini_divisor(res)
        if n > 1:
            res = '%d[%s]' % (n, d[i][loc])
        k = max(range(i + 1, j), key=lambda k: len(d[i][k] + d[k][j]))
        res = min([d[i][k] + d[k][j], res], key=len)
        d[i][j] = res

# 递归也可以, 不过需要重复计算
dfs(s: str):
    if len(s) < 5:
        return s
    else:
        # 找n倍的字符串, 这里还有一个技巧, 见字符串的最小约数集合
        n, slice = find_mini_divisor(s)
        res = '%d[%s]' % (n, slice)
        s[:k] =

    """

    def encode(self, s: str) -> str:
        d = [[s[i:j] if j > i else None for j in range(0, len(s) + 1)] for i in range(len(s))]
        for size in range(5, len(s) + 1):
            for i in range(len(s)):
                j = i + size
                if j > len(s):
                    break
                res = s[i:j]
                n, ss, loc = Solution2.find_mini_divisor(res)
                if n > 1:
                    res = '%d[%s]' % (n, d[i][i + loc])
                cc = [d[i][k_] + d[k_][j] for k_ in range(i + 1, j)]
                cc.append(res)
                mm = min(cc, key=len)
                d[i][j] = mm
        return d[0][len(s)]

    @staticmethod
    def find_mini_divisor(string: str) -> Optional[Tuple[int, str, int]]:
        """
        找到重复的字串, n*字串=string, 该字串是最小的
        :param string:
        :return:
        """
        loc_ = (string * 2).find(string, 1)
        return len(string) // loc_, string[:loc_], loc_


solution1 = Solution1()
assert solution1.encode('aaa') == 'aaa'
assert solution1.encode("aaaaa") == '5[a]'
assert solution1.encode("aabcaabcd") == '2[aabc]d'
assert solution1.encode('aaaaaaaaaa') == '10[a]'
assert solution1.encode("abbbabbbcabbbabbbc") == "2[2[abbb]c]"
assert solution1.encode("abeedbbbdbbbbbb") == "abeedbbbd6[b]"
assert solution1.encode("abcdcdcdabcdcdcdxyxyxyxy") == "2[ab3[cd]]4[xy]"

solution2 = Solution2()
assert solution2.encode('aaa') == 'aaa'
assert solution2.encode("aaaaa") == '5[a]'
assert solution2.encode("aabcaabcd") == '2[aabc]d'
assert solution2.encode('aaaaaaaaaa') == 'a9[a]'
assert solution2.encode("abbbabbbcabbbabbbc") == "2[2[abbb]c]"
assert solution2.encode("abeedbbbdbbbbbb") == "abeedbbbd6[b]"
assert solution2.encode("abcdcdcdabcdcdcdxyxyxyxy") == "2[ab3[cd]]4[xy]"
assert solution2.encode("aaaaaaaaaabbbaaaaabbb") == "5[a]2[5[a]bbb]"
